package com.gozap.dynmicrogram.example;

/**
 * 
 * 矩阵相乘，计算最小计算量程序。采用动态规划方式
 * 
 * @author yaoming
 * @date 2013-1-15 下午02:24:42
 * @since JDK1.6
 * @version 2.0.0
 */
public class Matrix {

	// 先计算后面两个要优于先计算前面两个
	int[] arr = { 100, 5, 50, 10, 20 };

	public void caculate() {
		int matrixLen = arr.length - 1;
		// 记录最小值min[a][b]代表下标为a到下标为b的最小值
		int[][] min = new int[matrixLen][matrixLen];

		int[][] record = new int[matrixLen][matrixLen];
		// 设置斜线
		for (int i = 0; i < matrixLen; i++) {
			min[i][i] = 0;
		}
		// 临时值
		int t;
		// 最小值
		int m = Integer.MAX_VALUE;

		int a = Integer.MAX_VALUE;
		// 最外层是长度为2一直到长度为全长，长度为1的已经设置了
		for (int L = 2; L <= matrixLen; L++) {
			// 从下标0开始长度为L的最小量计算出来
			for (int i = 0; i <= matrixLen - L; i++) {
				m = Integer.MAX_VALUE;
				// 计算下标i到下标i+L-1
				for (int k = i; k < L + i - 1; k++) {
					t = min[i][k] + min[k + 1][i + L - 1] + arr[i] * arr[k + 1] * arr[i + L];
					if (t < m) {
						m = t;
						a = k;
					}
				}
				record[i][i + L - 1] = a;
				min[i][i + L - 1] = m;
			}
		}
		System.out.println(m);
	}

	public void print(int[][] record) {
		// 打印分隔轨迹
		// 找到record[0][len-1],根据这个值a看从哪里分隔，比如a=2，则看record[0][2]和record[3][len-1]
		// 如此可以从顶部一直找到底部
	}

	public static void main(String[] args) {

		Matrix matrix = new Matrix();
		matrix.caculate();
	}
}
